TD 10 : perte de DF et 3ème Forme Normale (FN3)

Projection de DF, Perte de DF, FN3

Fermetures transitives

Clés

Projection de DF

Perte de DF

FN3

Published

December 5, 2025

Avec solutions

L3 MIASHS

Université Paris Cité

Année 2025

Course Homepage

Moodle

Exercice 1

Soit le schéma $\mathcal{A}=\{A,B,C,D,E,F\}$ et l’ensemble de dépendances fonctionnelles \[\Sigma = \{ AB\to C, BC\to AD, D\to E, CF\to B\}\]

Calculer la fermeture $\left\{A,B\right\}^+$.
Est-ce que $\Sigma$ implique la dépendance fonctionnelle $AB\to D$ ?
Est-ce que $\Sigma$ implique la dépendance fonctionnelle $D\to A$ ?

Solution

On obtient $\left\{A,B\right\}^+=\left\{A,B,C,D,E\right\}$.
Oui car $D\in\left\{A,B\right\}^+$
Non car $\left\{D\right\}^+=\left\{D,E\right\}$ ne contient pas $A$.

Cours : projection de dépendance fonctionnelle

Définition

Soient $\mathcal{A}$ un schéma, $X \subset \mathcal{A}$ et $\Sigma$ un ensemble de dépendances fonctionnelles.

$X$ est une sur-clé (super-clé) de $\mathcal{A}$ relativement à $\Sigma$ si $X^+ = \mathcal{A}$.
$X$ est une clé de $\mathcal{A}$ relativement à $\Sigma$ si $X$ est une sur-clé (super-clé) minimale au sens de l’inclusion.

Propriété

Soit $\mathcal{A}$ un schéma, $\Sigma_1$ et $\Sigma_2$ deux ensembles de DF sur $\mathcal{A}$.

$\Sigma_1$ et $\Sigma_2$ sont équivalents si et seulement si $\quad \forall X \subset \mathcal{A},\ \ X^+_{\Sigma_1} = X^+_{\Sigma_2}$

où $X^+_{\Sigma_1}$ et $X^+_{\Sigma_2}$ sont les fermetures transitives de $X$ respectivement selon $\Sigma_1$ et $\Sigma_2$.

justification

Cette propriété dit que $\Sigma_1$ et $\Sigma_2$ sont équivalents si et seulement si, pour tout ensemble d’attributs $X$ , les ensembles $X^+$ de tous les attributs déterminés par $X$ sont identiques selon $\Sigma_1$ et selon $\Sigma_2$.

Définition

Soient $\mathcal{A}$ et $\mathcal{A}_1$ deux shémas tels que $\mathcal{A}_1 \subset \mathcal{A}$.

On appelle projection de $\Sigma$ sur $\mathcal{A}_1$ et on note $\pi_{\mathcal{A}_1}(\Sigma)$ l’ensemble des DF $X\to Y$ impliquées par $\Sigma$ telles que $X\subset\mathcal{A}_1$ et $Y\subset\mathcal{A}_1$.

Autrement dit, $\pi_{\mathcal{A}_1}(\Sigma)$ est l’ensemble des dépendances impliquées par $\Sigma$ qui sont locales à $\mathcal{A}_1$.

Algorithme de calcul de $\pi_{\mathcal{A}_1}(\Sigma)$

Un ensemble de DF équivalent à $\pi_{\mathcal{A}_1}(\Sigma)$ est l’ensemble des DF

$X\to (X^+\cap\mathcal{A}_1)\setminus X$ telles que $X\subset\mathcal{A}_1$, $X\not=\emptyset$ et $X\not=\mathcal{A}_1$

Exemple

Soient $\mathcal{A}=\left\{A,B,C,D,E\right\}$ un schéma, $\mathcal{A}_1=\left\{A,B,C\right\}$ et

$\Sigma=\left\{AB\to DE, C\to E, D\to C, E\to A\right\}$

On utilise l’algorithme vu en cours pour calculer la fermeture transitive.

$A^+=A$, on n’ajoute rien car $A\rightarrow A$ est triviale.
$B^+=B$, idem.
$C^+=CEA$, $C\rightarrow C$ est triviale et $E \notin \mathcal{A}_1$ donc on ajoute $C\to A$,
$AB^+=ABDEC$, on ajoute $AB\to C$,
$AC^+=ACE$, on n’ajoute rien.
$BC^+=BCEAD$, on obtient $BC\to A$, mais $BC\to A$ se déduit de $C\to A$ déjà présent, donc on n’ajoute rien.

Donc $\pi_{\mathcal{A}_1}(\Sigma)$ est équivalent à $\left\{C\to A, AB\to C\right\}$.

C’est un ensemble minimal de DF élémentaires qui engendrent $\pi_{\mathcal{A}_1}(\Sigma)$, c’est à dire que l’on ne peut pas supprimer d’attribut dans une DF en conservant une DF équivalente (concept de DF élémentaire), et on ne peut pas réduire l’ensemble des DF en conservant une famille génératrice (concept d’ensemble minimal).

$\mathcal{A}_1$ a pour clés $BC$ ou $AB$.

Exercice 3

Soient $\mathcal{A}=\left\{A,B,C,D,E\right\}$ un schéma et $\mathcal{A}_1=\left\{A,B,C\right\}$.

Pour chaque ensemble $\Sigma$ de dépendances fonctionnelles ci-dessous, déterminer un ensemble minimal de DF élémentaires équivalent à $\pi_{\mathcal{A}_1}(\Sigma)$ et donner la liste des clés possibles pour $\mathcal{A}_1$ relativement à $\Sigma$.

$\Sigma=\left\{A\to D, BD\to E, AC\to E, DE\to B\right\}$
$\Sigma=\left\{AB\to D, AC\to E, BC\to D, D\to A, E\to B\right\}$
$\Sigma=\left\{A\to B, B\to C, C\to D, D\to E, E\to A\right\}$

Solution

- $A^+=AD$, $B^+=B$, $C^+=C$ rien à ajouter,
- $AB^+=ABDE$, $AC^+=ACDEB$ donc on ajoute $AC \to B$,
- $BC^+=BC$.
Donc $\pi_{\mathcal{A}_1}(\Sigma)$ est équivalent à $\left\{AC \to B\right\}$.

$\mathcal{A}_1$ a pour unique clé $AC$.
- $A^+=A$, $B^+=B$, $C^+=C$ rien à ajouter,
- $AB^+=ABD$, $AC^+=ACEBD$ donc on ajoute $AC \to B$,
- $BC^+=BCDAE$ donc on ajoute $BC \to A$.
Donc $\pi_{\mathcal{A}_1}(\Sigma)$ est équivalent à $\left\{AC \to B, BC\to A\right\}$.

$\mathcal{A}_1$ a pour clés $AC$, $BC$.
Tout attribut est une clef de $\mathcal{A}$, donc c’est aussi le cas pour $\mathcal{A}_1$.

$\pi_{\mathcal{A}_1}(\Sigma)$ est donc équivalent à $\left\{A\to B, B\to C, C\to A\right\}$.

Cours : décomposition et perte de dépendance

Dans un système de BDD relationnelles, les données sont représentées par des tuples qui décrivent des relations. Lorsqu’on définit des tables dans une base de données, on décompose ces relations en plusieurs relations $R_1$, $R_2$, $\dots$, les tables de la BDD.

Lors d’une telle décomposition, on se pose 3 questions fondamentales :

Y-a-t-il perte de dépendance fonctionnelle ?
Y-a-t-il perte d’informations ?
Y-a-t-il redondance de l’information ?

Définition

Soit $\mathcal{A}$ un schéma, on dit que $\left\{\mathcal{A}_1,\dots ,\mathcal{A}_k\right\}$ est une décomposition de $\mathcal{A}$ si et seulement si,

pour tout $i$, $\mathcal{A}_i \not=\emptyset$,
${\displaystyle \bigcup_{i=1}^k \mathcal{A}_i = \mathcal{A}}$

Définition : préservation de DF

Soit un schéma $\mathcal{A}$ et une décomposition $\left\{\mathcal{A}_1,\dots ,\mathcal{A}_k\right\}$.

La DF $X\to Y$ est préservée si et seulement la fermeture de $X$ par rapport à la réunion des DF locales ${\displaystyle \bigcup_{i=1}^k \pi_{\mathcal{A}_i}(\Sigma)}$ contient $Y$.

Algorithme pour vérifier la préservation de $X\to Y$

Pour calculer la fermeture de $X$ par rapport aux DF locales ${\displaystyle \bigcup_{i=1}^k \pi_{\mathcal{A}_i}(\Sigma)}$, on peut utiliser l’algorithme suivant :

Initialisation $Z := X$
Tant que $Z$ grandit : pour $i=1,\dots,k$, $Z := Z \cup\bigl( (Z\cap \mathcal{A}_i)^+_\Sigma \cap \mathcal{A}_i\bigr)$

L’ensemble $Z$ obtenu est la fermeture recherchée.

L’intérêt de cet algorithme est qu’il n’est pas nécessaire de calculer les DF locales.

Si au cours du calcul on obtient que $Y\subset Z$, on peut conclure immédiatement que $X\to Y$ est préservée.

Exemple

Soient $\mathcal{A}=\left\{A,B,C,D,E\right\}$ un schéma, $\Sigma=\left\{B\rightarrow E, CE\rightarrow A\right\}$ et la décomposition $\left\{\mathcal{A}_1,\mathcal{A}_2,\mathcal{A}_3\right\}$ avec \[\mathcal{A}_1=\left\{A,B,C\right\}, \mathcal{A}_2=\left\{B,C,D\right\}, \mathcal{A}_3=\left\{A,C,E\right\}\]

Quelles dépendances de $\Sigma$ sont préservées ?

$CE\to A$ est préservée puisqu’elle est locale à $\mathcal{A}_3$.
$B\to E$ n’est pas préservée puisque, en utilisant l’algorithme précédent, on obtient :
- $Z := B$ puis $(B\cap\mathcal{A}_1)^+\cap\mathcal{A}_1$,
- donc $Z := B$ puis $B^+\cap\mathcal{A}_2=BE\cap\mathcal{A}_2=B$,
- donc $Z := B$ puis $(B\cap\mathcal{A}_3)^+\cap\mathcal{A}_3=\emptyset$
- donc $Z := B$. On a étudié toutes les projections sans accroître $Z$ donc on sort de la boucle “tant que”.
- A la fin de l’algorithme, $Z$ ne contient pas $E$ donc la dépendance $B\to E$ n’est pas préservée.

Exercice 4

Soient $\mathcal{A}=\left\{A,B,C,D,E\right\}$ un schéma décomposé en $\left\{\mathcal{A}_1,\mathcal{A}_2,\mathcal{A}_3\right\}$ avec \[\mathcal{A}_1=\left\{A,B,C\right\}\quad \mathcal{A}_2=\left\{B,C,D\right\}\quad \mathcal{A}_3=\left\{A,C,E\right\}\] Pour chaque ensemble $\Sigma$ de dépendances fonctionnelles ci-dessous, déterminer quelles dépendances sont préservées par cette décomposition, c’est-à-dire quelles DF de $\Sigma$ sont impliquées par ${\displaystyle\bigcup_{i=1}^3 \pi_{\mathcal{A}_i}(\Sigma)}$.

$\Sigma=\left\{AC\rightarrow E, BC\to D\right\}$
$\Sigma=\left\{A\rightarrow D, D\to E, B\to D\right\}$
$\Sigma=\left\{A\rightarrow D, CD\to E, E\to D\right\}$

Solution

$\Sigma=\left\{AC\rightarrow E, BC\to D\right\}$ est préservé puisqu’il ne contient que des DF locales.
$\Sigma=\left\{A\rightarrow D, D\to E, B\to D\right\}$. $B\to D$ est préservée
$\Sigma=\left\{A\rightarrow D, CD\to E, E\to D\right\}$. Aucune DF n’est préservée

Cours : Formes Normales 1 à 3

Définition : forme normale 1 (FN1)

Un schéma relationnel $\mathcal{A}$ est en forme normale 1 (FN1) si tous les attributs ont des valeurs atomiques (pas de liste de valeurs).

Idée de la forme normale 2 (FN2)

Un schéma relationnel est en deuxième forme normale (FN2) si elle est en FN1 et si tout attribut non identifiant (extérieur à une clé) ne dépend pas d’une partie d’une clé mais de toute la clé.

La FN2 assure seulement une non-redondance partielle de l’information.

Définition : forme normale 2 (FN2)

Un schéma relationnel $\mathcal{A}$ en FN1 est en forme normale 2 (FN2) relativement à un ensemble de DF $\Sigma$ ssi

pour toute clé $X$ et tout $Y$ non inclus dans $X$, il n’existe pas $X'$ strictement inclus dans $X$ tel que $X' \to Y$.

Méthode pour vérifier la FN2

Pour toute clé $X$, vérifier que la fermeture de tout sous-ensemble strict de $X$ par rapport à la projection des dépendances est inclus dans $X$.

Idée de la forme normale 3 (FN3)

Un schéma relationnel est en troisième forme normale (FN3) si elle est en FN2 et si tous les attributs non identifiants (extérieur à une clé) dépendent directement d’une clé et pas par transitivité via des attributs qui ne sont pas dans une clé , autrement dit elle est en FN3 s’il n’existe pas de dépendance fonctionnelle entre deux attributs non clés.

La FN3 assure une non-redondance partielle acceptable de l’information.

Définition : forme normale 3 (FN3)

Un schéma relationnel $\mathcal{A}$ en FN1 est en forme normale 3 (FN3) relativement à un ensemble de DF $\Sigma$ ssi pour toute dépendance non triviale $X \to Y$ de $\Sigma$, on a

le membre gauche $X$ est une sur-clé (super-clé)
ou le membre droit $Y$ fait partie d’une clé.

Méthode pour vérifier la FN3

Vérifier sur une famille génératrice de $\Sigma$ que chaque DF vérifie la règle FN3.

Exercice 5

On considère le schéma $\mathcal{A}$={}$.

Un nuplet/tuple $\verb!(o, a, n, np, nr, p)!$ a la signification suivante : la personne o habite à l’adresse a l’appartement de numéro n avec np personnes ayant nr pièces dont le propriétaire est p.

$\mathcal{A}$ vérifie l’ensemble $\Sigma$ des dépendances fonctionnelles suivantes

Occupant → Adresse
Occupant → Noapt
Occupant → Nbpersonnes
Adresse → Propriétaire
Adresse, Noapt → Occupant
Adresse, Noapt → Nbpièces

Pour chacune des décompositions suivantes, répondre aux questions :

La décomposition est-elle sans perte de DF ?
Déterminer la ou les clés de chaque sous-schéma $\mathcal{A_i}$.
Le schéma est-il en FN1, FN2, FN3 ?

Décomposition 1 : $\mathcal{A}$ n’est pas décomposée.
Décomposition 2 :
- $\mathcal{A_1}$ = {Occupant, Adresse, Noapt, Nbpersonnes, Propriétaire},
- $\mathcal{A_2}$ = {Adresse, Noapt, Occupant, Nbpièces}.
Décomposition 2 bis :
- $\mathcal{A_1}$ = {Occupant, Adresse, Nbpersonnes, Propriétaire},
- $\mathcal{A_2}$ = {Adresse, Noapt, Occupant, Nbpièces}.
Décomposition 3 :
- $\mathcal{A_1}$ = {Occupant, Adresse, Noapt, Nbpersonnes},
- $\mathcal{A_2}$ = {Adresse, Noapt, Occupant, Nbpièces},
- $\mathcal{A_3}$ = {Adresse, Propriétaire}.

Solution

Notation : $X^+_i$ désigne la fermeture de $X$ par rapport à la projection des DF sur $\mathcal{A}_i$.

Décomposition 1

$\mathcal{A}$ n’est pas décomposée.

La décomposition est donc sans perte de DF.
$\mathcal{A}$ dispose de 2 clés candidates : {Occupant} ou {Adresse, Noapt}.
- Le schéma est en FN1.
- Il n’est pas en FN2 car {Adresse}$^+$ = {Adresse, Propriétaire}.
- Il n’est pas en FN3 car il n’est pas en FN2, ou directement Adresse $\to$ Propriétaire ne respecte pas la FN3.

Décomposition 2

$\mathcal{A_1}$ = {Occupant, Adresse, Noapt, Nbpersonnes, Propriétaire},
$\mathcal{A_2}$ = {Adresse, Noapt, Occupant, Nbpièces}

La décomposition est sans perte de DF car toutes les dépendances sont locales à au moins un sous-schéma.
- $\mathcal{A_1}$ a deux clés : {Occupant} et {Adresse, Noapt},
- $\mathcal{A_2}$ a deux clés : {Occupant} et {Adresse, Noapt}.
- Le schéma est en FN1.
- - $\mathcal{A_1}$ n’est pas en FN2 car {Adresse}$^+_1$ = {Adresse, Propriétaire}.
  - $\mathcal{A_2}$ est en FN2 car {Adresse}$^+_2$ = {Adresse} et {Noapt}$^+_2$ = {Noapt}.
- - $\mathcal{A_1}$ n’est pas en FN3 il n’est pas en FN2, ou directement Adresse $\to$ Propriétaire ne respecte pas la FN3.
  - $\mathcal{A_2}$ est en FN3.

Décomposition 2 bis

$\mathcal{A_1}$ = {Occupant, Adresse, Nbpersonnes, Propriétaire},
$\mathcal{A_2}$ = {Adresse, Noapt, Occupant, Nbpièces}

La décomposition est sans perte de DF car toutes les dépendances sont locales à au moins un sous-schéma.
- $\mathcal{A_1}$ a une clé : {Occupant}
- $\mathcal{A_2}$ a deux clés : {Occupant} et {Adresse, Noapt}.
- Le schéma est en FN1.
- - $\mathcal{A_1}$ est en FN2 car sa seule clé ne contient qu’un attribut.
  - $\mathcal{A_2}$ est en FN2 car {Adresse}$^+_2$ = {Adresse} et {Noapt}$^+_2$ = {Noapt}.
- - $\mathcal{A_1}$ n’est pas en FN3 car la DF Adresse $\to$ Propriétaire ne respecte pas la FN3.
  - $\mathcal{A_2}$ est en FN3.

Décomposition 3

$\mathcal{A_1}$ = {Occupant, Adresse, Noapt, Nbpersonnes},
$\mathcal{A_2}$ = {Adresse, Noapt, Occupant, Nbpièces},
$\mathcal{A_3}$ = {Adresse, Propriétaire}.

La décomposition est sans perte de DF car toutes les dépendances sont locales à au moins un sous-schéma.
- $\mathcal{A_1}$ a deux clés : {Adresse, Noapt} et {Occupant},
- $\mathcal{A_2}$ a deux clés : {Adresse, Noapt} et {Occupant},
- $\mathcal{A_3}$ a une clé : {Adresse}.
- Le schéma est en FN1.
- - $\mathcal{A_1}$ est en FN2 car {Adresse}$^+_1$ = {Adresse} et {Noapt}$^+_1$ = {Noapt}.
  - $\mathcal{A_2}$ est en FN2 car {Adresse}$^+_2$ = {Adresse} et {Noapt}$^+_2$ = {Noapt}.
  - $\mathcal{A_3}$ est en FN2 car sa clé ne contient qu’un attribut.
- $\mathcal{A_1}$, $\mathcal{A_2}$ et $\mathcal{A_3}$ sont en FN3 car les règles de dépendance données vérifient toutes la FN3.

Other Formats

Exercice 1

Cours : projection de dépendance fonctionnelle

Exercice 3

Cours : décomposition et perte de dépendance

Exercice 4

Cours : Formes Normales 1 à 3

Exercice 5

Décomposition 1

Décomposition 2

Décomposition 2 bis

Décomposition 3